/**
 * 91. 解码问题
 */
public class Exercise4 {
    public int numDecodings(String s) {
        // 状态表达式 dp[i]: 到达i位置后，解码方式的总数
        // dp[i]位置的单或者和i-1位置成双进组合
        // 创建dp
        int n = s.length();
        char[] ss = s.toCharArray();
        // 比ss数组多一位
        int[] dp = new int[n + 1];

        // 初始化
        // 只需要初始化0下标，因为用到辅助节点。比正常多出一位
        dp[0] = 1;
        if(ss[0] - '0' != 0) {
            dp[1] = 1;
        }
        for(int i = 2;i <= n;i++) {
            if(ss[i - 1] - '0' != 0) {
                dp[i] += dp[i - 1];
            }
            int t = (ss[i - 2] - '0') * 10 + (ss[i - 1] - '0');
            if(t >= 10 && t <= 26) {
                dp[i] += dp[i - 2];
            }
        }
        return dp[n];
    }
}
